package com.zhugang.week07;

import java.util.PriorityQueue;

/**
 * @program algorithms
 * @description: kClosest
 * @author: chanzhugang
 * @create: 2022/08/02 11:39
 */
public class KClosest {

    /**
     * 973 最接近原点的K个点
     *
     * @param points
     * @param k
     * @return
     */
    public int[][] kClosest(int[][] points, int k) {
        // 没理解
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);

        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});

        }
        int n = points.length;
        for (int i = k; i < n; i++) {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (dist < pq.peek()[0]) {
                pq.poll();
                pq.offer(new int[]{dist, i});
            }
        }

        int[][] ans = new int[k][2];
        for (int i = 0; i < k; i++) {
            ans[i] = points[pq.poll()[1]];
        }
        return ans;
    }
}